{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sentence Screen Fitting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wordsTyping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #屏幕可显示句子的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>rows x cols</code> 的屏幕和一个用 <strong>非空 </strong>的单词列表组成的句子，请你计算出给定句子可以在屏幕上完整显示的次数。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>一个单词不能拆分成两行。</li>\n",
    "\t<li>单词在句子中的顺序必须保持不变。</li>\n",
    "\t<li><strong>在一行中 </strong>的两个连续单词必须用一个空格符分隔。</li>\n",
    "\t<li>句子中的单词总量不会超过 100。</li>\n",
    "\t<li>每个单词的长度大于 0 且不会超过 10。</li>\n",
    "\t<li>1 &le; <code>rows</code>, <code>cols</code> &le; 20,000.</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "rows = 2, cols = 8, 句子 sentence = [&quot;hello&quot;, &quot;world&quot;]\n",
    "\n",
    "<strong>输出：</strong>\n",
    "1\n",
    "\n",
    "<strong>解释：</strong>\n",
    "hello---\n",
    "world---\n",
    "\n",
    "<strong>字符 &#39;-&#39; 表示屏幕上的一个空白位置。</strong>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "rows = 3, cols = 6, 句子 sentence = [&quot;a&quot;, &quot;bcd&quot;, &quot;e&quot;]\n",
    "\n",
    "<strong>输出：</strong>\n",
    "2\n",
    "\n",
    "<strong>解释：</strong>\n",
    "a-bcd- \n",
    "e-a---\n",
    "bcd-e-\n",
    "\n",
    "<strong>字符 &#39;-&#39; 表示屏幕上的一个空白位置。</strong>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "rows = 4, cols = 5, 句子 sentence = [&quot;I&quot;, &quot;had&quot;, &quot;apple&quot;, &quot;pie&quot;]\n",
    "\n",
    "<strong>输出：</strong>\n",
    "1\n",
    "\n",
    "<strong>解释：</strong>\n",
    "I-had\n",
    "apple\n",
    "pie-I\n",
    "had--\n",
    "\n",
    "<strong>字符 &#39;-&#39; 表示屏幕上的一个空白位置。</strong>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sentence-screen-fitting](https://leetcode.cn/problems/sentence-screen-fitting/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sentence-screen-fitting](https://leetcode.cn/problems/sentence-screen-fitting/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"hello\",\"world\"]\\n2\\n8', '[\"a\", \"bcd\", \"e\"]\\n3\\n6', '[\"i\",\"had\",\"apple\",\"pie\"]\\n4\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        n = len(sentence)   \n",
    "        ############（2） 之所以计算这个，是因为下面的（1）需要\n",
    "        sentence_cnt = [0 for _ in range(n)]\n",
    "        next_word = [0 for _ in range(n)]\n",
    "\n",
    "        for i in range(n):      #如果以第i个单词为行首，进行填充\n",
    "            ID = i          #第i个word作为行首\n",
    "            c_idx = 0       #在当前行的index\n",
    "            remain_space = cols #剩余空间\n",
    "            while len(sentence[ID]) <= remain_space:\n",
    "                remain_space -= (len(sentence[ID]) + 1)\n",
    "                ID += 1\n",
    "                if ID == n:\n",
    "                    sentence_cnt[i] += 1    #ID到最后一个word了，sentence就过了一遍了\n",
    "                    ID = 0      #从第0个word开始了\n",
    "            next_word[i] = ID\n",
    "        \n",
    "        res = 0\n",
    "        ############ （1） 计算的预处理过程，在（2）中\n",
    "        ID = 0\n",
    "        for _ in range(rows):\n",
    "            res += sentence_cnt[ID]\n",
    "            ID = next_word[ID]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        def cal(start):\n",
    "            index = start\n",
    "            remain = cols\n",
    "            while remain > 0:\n",
    "                cur = index % len(sentence)\n",
    "\n",
    "                if remain < len(sentence[cur]):\n",
    "                    break\n",
    "                else:\n",
    "                    index += 1\n",
    "                    remain -= 1+len(sentence[cur])\n",
    "            return index - start\n",
    "        \n",
    "        store = {}\n",
    "        length = len(sentence)\n",
    "        for i in range(length):\n",
    "            store[i] = cal(i)\n",
    "        print()\n",
    "        tmp = 0\n",
    "        idt=0\n",
    "        for r in range(rows):\n",
    "            line_use=store[idt]\n",
    "            new_idt=idt+line_use\n",
    "            tmp+=new_idt//len(sentence)\n",
    "\n",
    "            idt=new_idt%len(sentence)\n",
    " \n",
    "        return tmp\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        n = len(sentence)\n",
    "        f = defaultdict(tuple)\n",
    "        def func(i):\n",
    "            if i in f:\n",
    "                return f[i]\n",
    "            j = i \n",
    "            l = 0 \n",
    "            cnt = 0 \n",
    "            while l + len(sentence[j]) <= cols:\n",
    "                l += len(sentence[j])\n",
    "                j = (j + 1) % n\n",
    "                if j == 0:\n",
    "                    cnt += 1\n",
    "                if l < cols:\n",
    "                    l += 1\n",
    "            \n",
    "            f[i] = (cnt, j)\n",
    "            #print(i, cnt) \n",
    "            return f[i] \n",
    "        pos = 0\n",
    "        tot = 0 \n",
    "        for _ in range(rows):\n",
    "            amt, pos = func(pos) \n",
    "            tot += amt \n",
    "        #print(f) \n",
    "        return tot \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "\n",
    "        def cal(start):\n",
    "            index = start\n",
    "\n",
    "            remian = cols\n",
    "            while remian > 0:\n",
    "                cur = index % len(sentence)\n",
    "                if remian < len(sentence[cur]):\n",
    "                    break\n",
    "                else:\n",
    "                    index += 1\n",
    "                    remian -= 1 + len(sentence[cur])\n",
    "            return index - start\n",
    "        \n",
    "        store = {}\n",
    "        length = len(sentence)\n",
    "        for i in range(length):\n",
    "            store[i] = cal(i)\n",
    "        \n",
    "        tmp = 0\n",
    "        for i in range(rows):\n",
    "            cur = tmp % length\n",
    "            move = store[cur]\n",
    "            tmp += move\n",
    "        return tmp // length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        n = len(sentence)\n",
    "        f = defaultdict(tuple)\n",
    "        def func(i):\n",
    "            if i in f:\n",
    "                return f[i]\n",
    "            j = i \n",
    "            l = 0 \n",
    "            cnt = 0 \n",
    "            while l + len(sentence[j]) <= cols:\n",
    "                l += len(sentence[j])\n",
    "                if j == n-1:\n",
    "                    cnt += 1\n",
    "                j = (j + 1) % n\n",
    "                if l < cols:\n",
    "                    l += 1\n",
    "            \n",
    "            f[i] = (cnt, j)\n",
    "            #print(i, cnt) \n",
    "            return f[i] \n",
    "        pos = 0\n",
    "        tot = 0 \n",
    "        for _ in range(rows):\n",
    "            amt, pos = func(pos) \n",
    "            tot += amt \n",
    "        #print(f) \n",
    "        return tot \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        s = ' '.join(sentence) + ' '\n",
    "        start = 0\n",
    "        for i in range(rows):\n",
    "            start += cols\n",
    "            if s[start % len(s)] == ' ':\n",
    "                start += 1\n",
    "            else:\n",
    "                while start > 0 and s[(start - 1) % len(s)] != ' ':\n",
    "                    start -= 1\n",
    "        return start // len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        n = len(sentence)\n",
    "        nexword=collections.Counter({i:0 for i in range(n)})\n",
    "        sentence_cnt=collections.Counter({i:0 for i in range(n)})\n",
    "        #print(sentence_cnt)\n",
    "        for i in range(n):\n",
    "            idx=i\n",
    "            remain_space=cols\n",
    "\n",
    "            while len(sentence[idx])<=remain_space:\n",
    "                remain_space=remain_space-len(sentence[idx])-1\n",
    "                idx+=1\n",
    "                if idx==n:\n",
    "                    idx=0\n",
    "                    sentence_cnt[i]+=1\n",
    "            nexword[i]=idx\n",
    "        #print(sentence_cnt)\n",
    "        #print(nexword)\n",
    "        ans=0\n",
    "        start=0\n",
    "        for i in range(rows):\n",
    "            ans+=sentence_cnt[start]\n",
    "            start=nexword[start]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def cal(start):\n",
    "            # 以sentence[start] 作为一行的开头，可以打出几个单词\n",
    "            index = start \n",
    "\n",
    "            remian = cols\n",
    "\n",
    "            while remian > 0:\n",
    "\n",
    "                cur = index % len(sentence)\n",
    "                # 当前行不足以打印当前单词\n",
    "                if remian < len(sentence[cur]):\n",
    "                    break\n",
    "                else:\n",
    "                    index += 1\n",
    "\n",
    "                    remian -= len(sentence[cur]) + 1 # remain - 剩余当前单词长度 + 空格 \n",
    "            \n",
    "            return index - start\n",
    "\n",
    "        \n",
    "        store = {}\n",
    "        for i in range(len(sentence)):\n",
    "            store[i] = cal(i)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(rows):\n",
    "            cur = res % len(sentence)\n",
    "            res += store[cur]\n",
    "        \n",
    "        return res // len(sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        sentence = ' '.join(sentence) + ' '\n",
    "        cursor = 0\n",
    "\n",
    "        for ii in range(rows):\n",
    "            cursor += cols # try moving to the row end\n",
    "\n",
    "            # move to the start of next word\n",
    "            if sentence[cursor % len(sentence)] == ' ':\n",
    "                cursor += 1\n",
    "            # in the middle of some word\n",
    "            # give up the word and move back\n",
    "            else:\n",
    "                while cursor > 0 and sentence[(cursor - 1) % len(sentence)] != ' ':\n",
    "                    cursor -= 1\n",
    "            \n",
    "        return cursor // len(sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        sentence=[len(item)+1 for item in sentence]\n",
    "        temp_word=0\n",
    "        res_cols=cols\n",
    "        ret=0\n",
    "        sentence_sum=sum(sentence)\n",
    "        for i in range(rows):\n",
    "            res_cols=cols\n",
    "            ret+=(res_cols//sentence_sum)\n",
    "            res_cols%=sentence_sum\n",
    "            while res_cols>=0:\n",
    "                if temp_word>=len(sentence):\n",
    "                    temp_word%=len(sentence)\n",
    "                    ret+=1\n",
    "                res_cols=res_cols-sentence[temp_word]\n",
    "                temp_word+=1\n",
    "            if res_cols!=-1:\n",
    "                temp_word-=1\n",
    "        if temp_word>=len(sentence):\n",
    "            ret+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        '''\n",
    "        for each word as a start of line\n",
    "        what's the next word start at next line\n",
    "        : given a wordi, we can infer next wordj start at next line\n",
    "        if j <= i: means we printed a sentence, add 1\n",
    "        # when j == i, means we can print a full sentence in one line\n",
    "        O(R) go through each rows\n",
    "        to calc every wordi to wordj: we need go through wordlist and each column\n",
    "        O(N*C)\n",
    "        time complexity = O(NC + R)\n",
    "        '''\n",
    "        maxWordLen = len(max(sentence, key=len))\n",
    "        if maxWordLen > cols:\n",
    "            return 0\n",
    "        def calcNextWordNextLine(i): # return idx and how many sentence can print\n",
    "            # if cannot contain next word j in left spaces, return j\n",
    "            nSentences = 0\n",
    "            leftSpaces = cols - len(sentence[i]) - 1  #4\n",
    "            j = (i+1) % len(sentence)\n",
    "            if j <= i:\n",
    "                nSentences += 1\n",
    "            while leftSpaces >= len(sentence[j]):\n",
    "                nextj = (j+1) % len(sentence)\n",
    "                if nextj <= j:\n",
    "                    nSentences += 1\n",
    "                leftSpaces = leftSpaces - (len(sentence[j]) + 1)\n",
    "                j = nextj\n",
    "            return j, nSentences\n",
    "\n",
    "        nextWordIndex = {}\n",
    "        for i, word in enumerate(sentence):\n",
    "            nextIdx, nSentences = calcNextWordNextLine(i)\n",
    "            nextWordIndex[i] = [nextIdx, nSentences]\n",
    "        curIdx = 0\n",
    "        totalSentences = 0\n",
    "        for r in range(rows):\n",
    "            nextIdx, nSentences = nextWordIndex[curIdx]\n",
    "            curIdx = nextIdx\n",
    "            totalSentences += nSentences\n",
    "        return totalSentences\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "\n",
    "        #计算第i个单词开始，下一行的第一个单词是哪个，中间经过了多少轮回\n",
    "        # def f(start):\n",
    "        #     n = 0\n",
    "        #     ls = cols - len(sentence[i]) - 1\n",
    "        #     j = (i + 1) % len(sentence) # 下一个单词\n",
    "        #     if j <= i:# 轮回\n",
    "        #         n += 1\n",
    "        #     while ls >= len(sentence[j]):\n",
    "        #         next_j = (j + 1) % len(sentence)\n",
    "        #         if nextj <= j:\n",
    "        #             n += 1\n",
    "                \n",
    "        def cal(start):\n",
    "            index = start\n",
    "            remain = cols\n",
    "            while remain > 0:\n",
    "                cur = index % len(sentence)\n",
    "                if remain < len(sentence[cur]):\n",
    "                    break\n",
    "                else:\n",
    "                    index += 1\n",
    "                    remain -= 1+len(sentence[cur])\n",
    "            return index - start\n",
    "        \n",
    "        store = {}\n",
    "        length = len(sentence)\n",
    "        for i in range(length):\n",
    "            store[i] = cal(i)\n",
    "        tmp = 0\n",
    "        for i in range(rows):\n",
    "            cur = tmp%length\n",
    "            move = store[cur]\n",
    "            tmp += move\n",
    "        return tmp // length       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        maxlen = 0\n",
    "        for i in sentence:\n",
    "            maxlen = max(maxlen , len(i))\n",
    "        if maxlen > cols: return 0\n",
    "        nextWord = [0 for i in range(len(sentence))]\n",
    "        jumpRow = [0 for i in range(len(sentence))]\n",
    "        for i in range (len(sentence)):\n",
    "            col = len(sentence[i])\n",
    "            nxt = i + 1\n",
    "            cnt = 0\n",
    "            if nxt >= len(sentence):\n",
    "                cnt += 1\n",
    "                nxt = 0\n",
    "            while nxt < len(sentence) and col + len(sentence[nxt]) + 1 <= cols:\n",
    "                col += 1 + len(sentence[nxt])\n",
    "                nxt += 1\n",
    "                if nxt >= len(sentence):\n",
    "                    nxt = 0\n",
    "                    cnt += 1\n",
    "            nextWord[i] = nxt\n",
    "            jumpRow[i] = cnt\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for i in range(rows):\n",
    "            nxt = nextWord[cur]\n",
    "            res += jumpRow[cur]\n",
    "            cur = nxt\n",
    "        #print(nextWord , jumpRow)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        def cal(start):\n",
    "            index = start\n",
    "            remain = cols\n",
    "            while remain > 0:\n",
    "                cur = index % len(sentence)\n",
    "                if remain < len(sentence[cur]):\n",
    "                    break\n",
    "                else:\n",
    "                    index += 1\n",
    "                    remain -= 1+len(sentence[cur])\n",
    "            return index - start\n",
    "        \n",
    "        store = {}\n",
    "        length = len(sentence)\n",
    "        for i in range(length):\n",
    "            store[i] = cal(i)\n",
    "        tmp = 0\n",
    "        for i in range(rows):\n",
    "            cur = tmp%length\n",
    "            move = store[cur]\n",
    "            tmp += move\n",
    "        return tmp // length  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:\n",
    "        n = len(sentence)\n",
    "        nexword=collections.Counter({i:0 for i in range(n)})\n",
    "        sentence_cnt=collections.Counter({i:0 for i in range(n)})\n",
    "        #print(sentence_cnt)\n",
    "        for i in range(n):\n",
    "            idx=i\n",
    "            remain_space=cols\n",
    "\n",
    "            while len(sentence[idx])<=remain_space:\n",
    "                remain_space=remain_space-len(sentence[idx])-1\n",
    "                idx+=1\n",
    "                if idx==n:\n",
    "                    idx=0\n",
    "                    sentence_cnt[i]+=1\n",
    "            nexword[i]=idx\n",
    "        print(sentence_cnt)\n",
    "        print(nexword)\n",
    "        ans=0\n",
    "        start=0\n",
    "        for i in range(rows):\n",
    "            ans+=sentence_cnt[start]\n",
    "            start=nexword[start]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
